Modelling equivalence with `Eq`

Yet again, we can model the notion of equality.

Equivalence relations capture the concept of equality of elements of the same type. The concept of an equivalence relation can be implemented in TypeScript with the following interface:

interface Eq<A> {
  readonly equals: (first: A, second: A) => boolean
}

Intuitively:

if equals(x, y) = true then we say x and y are equal
if equals(x, y) = false then we say x and y are different

Example

This is an instance of Eq for the number type:

import { Eq } from 'fp-ts/Eq'
import { pipe } from 'fp-ts/function'

const EqNumber: Eq<number> = {
  equals: (first, second) => first === second
}

pipe(EqNumber.equals(1, 1), console.log) // => true
pipe(EqNumber.equals(1, 2), console.log) // => false

The following laws have to hold true:

Reflexivity: equals(x, x) === true, for every x in A
Symmetry: equals(x, y) === equals(y, x), for every x, y in A
Transitivity: if equals(x, y) === true and equals(y, z) === true, then equals(x, z) === true, for every x, y, z in A

Quiz. Would a combinator reverse: <A>(E: Eq<A>) => Eq<A> make sense?

Quiz. Would a combinator not: <A>(E: Eq<A>) => Eq<A> make sense?

import { Eq } from 'fp-ts/Eq'

export const not = <A>(E: Eq<A>): Eq<A> => ({
  equals: (first, second) => !E.equals(first, second)
})

Example

Let's see the first example of the usage of the Eq abstraction by defining a function elem that checks whether a given value is an element of ReadonlyArray.

import { Eq } from 'fp-ts/Eq'
import { pipe } from 'fp-ts/function'
import * as N from 'fp-ts/number'

// returns `true` if the element `a` is included in the list `as`
const elem = <A>(E: Eq<A>) => (a: A) => (as: ReadonlyArray<A>): boolean =>
  as.some((e) => E.equals(a, e))

pipe([1, 2, 3], elem(N.Eq)(2), console.log) // => true
pipe([1, 2, 3], elem(N.Eq)(4), console.log) // => false

Why would we not use the native includes Array method?

console.log([1, 2, 3].includes(2)) // => true
console.log([1, 2, 3].includes(4)) // => false

Let's define some Eq instance for more complex types.

import { Eq } from 'fp-ts/Eq'

type Point = {
  readonly x: number
  readonly y: number
}

const EqPoint: Eq<Point> = {
  equals: (first, second) => first.x === second.x && first.y === second.y
}

console.log(EqPoint.equals({ x: 1, y: 2 }, { x: 1, y: 2 })) // => true
console.log(EqPoint.equals({ x: 1, y: 2 }, { x: 1, y: -2 })) // => false

and check the results of elem and includes

const points: ReadonlyArray<Point> = [
  { x: 0, y: 0 },
  { x: 1, y: 1 },
  { x: 2, y: 2 }
]

const search: Point = { x: 1, y: 1 }

console.log(points.includes(search)) // => false :(
console.log(pipe(points, elem(EqPoint)(search))) // => true :)

Quiz (JavaScript). Why does the includes method returns false?

-> See the answer here

Abstracting the concept of equality is of paramount importance, especially in a language like JavaScript where some data types do not offer handy APIs for checking user-defined equality.

The JavaScript native Set datatype suffers by the same issue:

type Point = {
  readonly x: number
  readonly y: number
}

const points: Set<Point> = new Set([{ x: 0, y: 0 }])

points.add({ x: 0, y: 0 })

console.log(points)
// => Set { { x: 0, y: 0 }, { x: 0, y: 0 } }

Given the fact that Set uses === ("strict equality") for comparing values, points now contains two identical copies of { x: 0, y: 0 }, a result we definitely did not want. Thus it is convenient to define a new API to add an element to a Set, one that leverages the Eq abstraction.

Quiz. What would be the signature of this API?

Does EqPoint require too much boilerplate? The good news is that theory offers us yet again the possibility of implementing an Eq instance for a struct like Point if we are able to define an Eq instance for each of its fields.

Conveniently the fp-ts/Eq module exports a struct combinator:

import { Eq, struct } from 'fp-ts/Eq'
import * as N from 'fp-ts/number'

type Point = {
  readonly x: number
  readonly y: number
}

const EqPoint: Eq<Point> = struct({
  x: N.Eq,
  y: N.Eq
})

Note. Like for Semigroup, we aren't limited to struct-like data types, we also have combinators for working with tuples: tuple

import { Eq, tuple } from 'fp-ts/Eq'
import * as N from 'fp-ts/number'

type Point = readonly [number, number]

const EqPoint: Eq<Point> = tuple(N.Eq, N.Eq)

console.log(EqPoint.equals([1, 2], [1, 2])) // => true
console.log(EqPoint.equals([1, 2], [1, -2])) // => false

There are other combinators exported by fp-ts, here we can see a combinator that allows us to derive an Eq instance for ReadonlyArrays.

import { Eq, tuple } from 'fp-ts/Eq'
import * as N from 'fp-ts/number'
import * as RA from 'fp-ts/ReadonlyArray'

type Point = readonly [number, number]

const EqPoint: Eq<Point> = tuple(N.Eq, N.Eq)

const EqPoints: Eq<ReadonlyArray<Point>> = RA.getEq(EqPoint)

Similarly to Semigroups, it is possible to define more than one Eq instance for the same given type. Suppose we have modeled a User with the following type:

type User = {
  readonly id: number
  readonly name: string
}

we can define a "standard" Eq<User> instance using the struct combinator:

import { Eq, struct } from 'fp-ts/Eq'
import * as N from 'fp-ts/number'
import * as S from 'fp-ts/string'

type User = {
  readonly id: number
  readonly name: string
}

const EqStandard: Eq<User> = struct({
  id: N.Eq,
  name: S.Eq
})

Several languages, even pure functional languages like Haskell, do not allow to have more than one Eq instance per data type. But we may have different contexts where the meaning of User equality might differ. One common context is where two Users are equal if their id field is equal.

/** two users are equal if their `id` fields are equal */
const EqID: Eq<User> = {
  equals: (first, second) => N.Eq.equals(first.id, second.id)
}

Now that we made an abstract concept concrete by representing it as a data structure, we can programmatically manipulate Eq instances like we do with other data structures. Let's see an example.

Example. Rather than manually defining EqId we can use the combinator contramap: given an instance Eq<A> and a function from B to A, we can derive an Eq<B>

import { Eq, struct, contramap } from 'fp-ts/Eq'
import { pipe } from 'fp-ts/function'
import * as N from 'fp-ts/number'
import * as S from 'fp-ts/string'

type User = {
  readonly id: number
  readonly name: string
}

const EqStandard: Eq<User> = struct({
  id: N.Eq,
  name: S.Eq
})

const EqID: Eq<User> = pipe(
  N.Eq,
  contramap((user: User) => user.id)
)

console.log(
  EqStandard.equals({ id: 1, name: 'Giulio' }, { id: 1, name: 'Giulio Canti' })
) // => false (because the `name` property differs)

console.log(
  EqID.equals({ id: 1, name: 'Giulio' }, { id: 1, name: 'Giulio Canti' })
) // => true (even though the `name` property differs)

console.log(EqID.equals({ id: 1, name: 'Giulio' }, { id: 2, name: 'Giulio' }))
// => false (even though the `name` property is equal)

Quiz. Given a data type A, is it possible to define a Semigroup<Eq<A>>? What could it represent?

Modeling ordering relations with `Ord`

In the previous chapter regarding Eq we were dealing with the concept of equality. In this one we'll deal with the concept of ordering.

The concept of a total order relation can be implemented in TypeScript as following:

import { Eq } from 'fp-ts/lib/Eq'

type Ordering = -1 | 0 | 1

interface Ord<A> extends Eq<A> {
  readonly compare: (x: A, y: A) => Ordering
}

Resulting in:

x < y if and only if compare(x, y) = -1
x = y if and only if compare(x, y) = 0
x > y if and only if compare(x, y) = 1

Example

Let's try to define an Ord instance for the type number:

import { Ord } from 'fp-ts/Ord'

const OrdNumber: Ord<number> = {
  equals: (first, second) => first === second,
  compare: (first, second) => (first < second ? -1 : first > second ? 1 : 0)
}

The following laws have to hold true:

Reflexivity: compare(x, x) <= 0, for every x in A
Antisymmetry: if compare(x, y) <= 0 and compare(y, x) <= 0 then x = y, for every x, y in A
Transitivity: if compare(x, y) <= 0 and compare(y, z) <= 0 then compare(x, z) <= 0, for every x, y, z in A

compare has also to be compatible with the equals operation from Eq:

compare(x, y) === 0 if and only if equals(x, y) === true, for every x, y in A

Note. equals can be derived from compare in the following way:

equals: (first, second) => compare(first, second) === 0

In fact the fp-ts/Ord module exports a handy helper fromCompare which allows us to define an Ord instance simply by supplying the compare function:

import { Ord, fromCompare } from 'fp-ts/Ord'

const OrdNumber: Ord<number> = fromCompare((first, second) =>
  first < second ? -1 : first > second ? 1 : 0
)

Quiz. Is it possible to define an Ord instance for the game Rock-Paper-Scissor where move1 <= move2 if move2 beats move1?

Let's see a practical usage of an Ord instance by defining a sort function which orders the elements of a ReadonlyArray.

import { pipe } from 'fp-ts/function'
import * as N from 'fp-ts/number'
import { Ord } from 'fp-ts/Ord'

export const sort = <A>(O: Ord<A>) => (
  as: ReadonlyArray<A>
): ReadonlyArray<A> => as.slice().sort(O.compare)

pipe([3, 1, 2], sort(N.Ord), console.log) // => [1, 2, 3]

Quiz (JavaScript). Why does the implementation leverages the native Array slice method?

Let's see another Ord pratical usage by defining a min function that returns the smallest of two values:

import { pipe } from 'fp-ts/function'
import * as N from 'fp-ts/number'
import { Ord } from 'fp-ts/Ord'

const min = <A>(O: Ord<A>) => (second: A) => (first: A): A =>
  O.compare(first, second) === 1 ? second : first

pipe(2, min(N.Ord)(1), console.log) // => 1

Dual Ordering

In the same way we could invert the concat operation to obtain the dual semigroup using the reverse combinator, we can invert the compare operation to get the dual ordering.

Let's define the reverse combinator for Ord:

import { pipe } from 'fp-ts/function'
import * as N from 'fp-ts/number'
import { fromCompare, Ord } from 'fp-ts/Ord'

export const reverse = <A>(O: Ord<A>): Ord<A> =>
  fromCompare((first, second) => O.compare(second, first))

A usage example for reverse is obtaining a max function from the min one:

import { flow, pipe } from 'fp-ts/function'
import * as N from 'fp-ts/number'
import { Ord, reverse } from 'fp-ts/Ord'

const min = <A>(O: Ord<A>) => (second: A) => (first: A): A =>
  O.compare(first, second) === 1 ? second : first

// const max: <A>(O: Ord<A>) => (second: A) => (first: A) => A
const max = flow(reverse, min)

pipe(2, max(N.Ord)(1), console.log) // => 2

The totality of ordering (meaning that given any x and y, one of the two conditions needs to hold true: x <= y or y <= z) may appear obvious when speaking about numbers, but that's not always the case. Let's see a slightly more complex scenario:

type User = {
  readonly name: string
  readonly age: number
}

It's not really clear when a User is "smaller or equal" than another User.

How can we define an Ord<User> instance?

That depends on the context, but a possible choice might be ordering Users by their age:

import * as N from 'fp-ts/number'
import { fromCompare, Ord } from 'fp-ts/Ord'

type User = {
  readonly name: string
  readonly age: number
}

const byAge: Ord<User> = fromCompare((first, second) =>
  N.Ord.compare(first.age, second.age)
)

Again we can get rid of some boilerplate using the contramap combinatorL given an Ord<A> instance and a function from B to A, it is possible to derive Ord<B>:

import { pipe } from 'fp-ts/function'
import * as N from 'fp-ts/number'
import { contramap, Ord } from 'fp-ts/Ord'

type User = {
  readonly name: string
  readonly age: number
}

const byAge: Ord<User> = pipe(
  N.Ord,
  contramap((_: User) => _.age)
)

We can get the youngest of two Users using the previously defined min function.

// const getYounger: (second: User) => (first: User) => User
const getYounger = min(byAge)

pipe(
  { name: 'Guido', age: 50 },
  getYounger({ name: 'Giulio', age: 47 }),
  console.log
) // => { name: 'Giulio', age: 47 }

Quiz. In the fp-ts/ReadonlyMap module the following API is exposed:

/**
 * Get a sorted `ReadonlyArray` of the keys contained in a `ReadonlyMap`.
 */
declare const keys: <K>(
  O: Ord<K>
) => <A>(m: ReadonlyMap<K, A>) => ReadonlyArray<K>

why does this API requires an instance for Ord<K>?

Let's finally go back to the very first issue: defining two semigroups SemigroupMin and SemigroupMax for types different than number:

import { Semigroup } from 'fp-ts/Semigroup'

const SemigroupMin: Semigroup<number> = {
  concat: (first, second) => Math.min(first, second)
}

const SemigroupMax: Semigroup<number> = {
  concat: (first, second) => Math.max(first, second)
}

Now that we have the Ord abstraction we can do it:

import { pipe } from 'fp-ts/function'
import * as N from 'fp-ts/number'
import { Ord, contramap } from 'fp-ts/Ord'
import { Semigroup } from 'fp-ts/Semigroup'

export const min = <A>(O: Ord<A>): Semigroup<A> => ({
  concat: (first, second) => (O.compare(first, second) === 1 ? second : first)
})

export const max = <A>(O: Ord<A>): Semigroup<A> => ({
  concat: (first, second) => (O.compare(first, second) === 1 ? first : second)
})

type User = {
  readonly name: string
  readonly age: number
}

const byAge: Ord<User> = pipe(
  N.Ord,
  contramap((_: User) => _.age)
)

console.log(
  min(byAge).concat({ name: 'Guido', age: 50 }, { name: 'Giulio', age: 47 })
) // => { name: 'Giulio', age: 47 }
console.log(
  max(byAge).concat({ name: 'Guido', age: 50 }, { name: 'Giulio', age: 47 })
) // => { name: 'Guido', age: 50 }

Example

Let's recap all of this with one final example (adapted from Fantas, Eel, and Specification 4: Semigroup).

Suppose we need to build a system where, in a database, there are records of customers implemented in the following way:

interface Customer {
  readonly name: string
  readonly favouriteThings: ReadonlyArray<string>
  readonly registeredAt: number // since epoch
  readonly lastUpdatedAt: number // since epoch
  readonly hasMadePurchase: boolean
}

For some reason, there might be duplicate records for the same person.

We need a merging strategy. Well, that's Semigroup's bread and butter!

import * as B from 'fp-ts/boolean'
import { pipe } from 'fp-ts/function'
import * as N from 'fp-ts/number'
import { contramap } from 'fp-ts/Ord'
import * as RA from 'fp-ts/ReadonlyArray'
import { max, min, Semigroup, struct } from 'fp-ts/Semigroup'
import * as S from 'fp-ts/string'

interface Customer {
  readonly name: string
  readonly favouriteThings: ReadonlyArray<string>
  readonly registeredAt: number // since epoch
  readonly lastUpdatedAt: number // since epoch
  readonly hasMadePurchase: boolean
}

const SemigroupCustomer: Semigroup<Customer> = struct({
  // keep the longer name
  name: max(pipe(N.Ord, contramap(S.size))),
  // accumulate things
  favouriteThings: RA.getSemigroup<string>(),
  // keep the least recent date
  registeredAt: min(N.Ord),
  // keep the most recent date
  lastUpdatedAt: max(N.Ord),
  // boolean semigroup under disjunction
  hasMadePurchase: B.SemigroupAny
})

console.log(
  SemigroupCustomer.concat(
    {
      name: 'Giulio',
      favouriteThings: ['math', 'climbing'],
      registeredAt: new Date(2018, 1, 20).getTime(),
      lastUpdatedAt: new Date(2018, 2, 18).getTime(),
      hasMadePurchase: false
    },
    {
      name: 'Giulio Canti',
      favouriteThings: ['functional programming'],
      registeredAt: new Date(2018, 1, 22).getTime(),
      lastUpdatedAt: new Date(2018, 2, 9).getTime(),
      hasMadePurchase: true
    }
  )
)
/*
{ name: 'Giulio Canti',
  favouriteThings: [ 'math', 'climbing', 'functional programming' ],
  registeredAt: 1519081200000, // new Date(2018, 1, 20).getTime()
  lastUpdatedAt: 1521327600000, // new Date(2018, 2, 18).getTime()
  hasMadePurchase: true
}
*/

Quiz. Given a type A is it possible to define a Semigroup<Ord<A>> instance? What could it possibly represent?

Demo

Modelling equivalence with Eq

Modeling ordering relations with Ord​

Dual Ordering​

Modelling equivalence with `Eq`

Modeling ordering relations with `Ord`

Dual Ordering